class Solution
{
public:
    vector<int> leftmostBuildingQueries(vector<int> &heights, vector<vector<int>> &queries)
    {
        int n = queries.size();
        vector<pair<vector<int>, int>> queriesWithIndex(n);
        for (int i = 0; i < n; ++i)
        {
            auto &query = queries[i];
            if (query[0] > query[1])
            {
                swap(query[0], query[1]);
            }
            queriesWithIndex[i] = {query, i};
        }
        sort(queriesWithIndex.begin(), queriesWithIndex.end(), [](const auto &a, const auto &b)
             { return a.first[1] < b.first[1]; });

        vector<int> ans(n);
        vector<int> s; // stack
        int back = heights.size() - 1;
        for (int i = n - 1; i >= 0; --i)
        {
            auto &query = queriesWithIndex[i].first;
            for (; back > query[1]; --back)
            {
                while (!s.empty() && heights[s.back()] <= heights[back])
                {
                    s.pop_back();
                }
                s.push_back(back);
            }
            if (query[0] == query[1] || heights[query[0]] < heights[query[1]])
            {
                ans[queriesWithIndex[i].second] = query[1];
            }
            else
            {

                auto pos = lower_bound(s.rbegin(), s.rend(), max(heights[query[0]], heights[query[1]]) + 1, [&](auto heightIndex, auto queryHeight)
                                       { return heights[heightIndex] < queryHeight; });
                if (pos == s.rend())
                {
                    ans[queriesWithIndex[i].second] = -1;
                }
                else
                {
                    ans[queriesWithIndex[i].second] = *pos;
                }
            }
        }
        return ans;
    }
};